#ifndef GRAFO_H
#define GRAFO_H

#include<vector>
#include<algorithm>
#include<list>
#include <ctime>
#include <sstream>

using namespace std;

#include "Nodo.h"

const int INF = 65536;

template<class T>
class Grafo{
    
    private:
        vector< Nodo<T> > nodos;
        //int coloreo( vector<unsigned> ordenNodos , vector< vector<int> > colores );
        
        
    public:
        Grafo( int cantNodos , T& obj );
        ~Grafo();
        
        void agregarArco( int nodoA , int nodoB , int longitud );
        void agregarNodo( T& obj );

        Nodo<T>& getNodo( int nodo );

        void getNodosAdyacentes( int nodo , vector< Nodo<T> >& vec );
        void getNodosAdyacentes( int nodo , vector<unsigned>& vec );
        bool esAdyacente( int nodoA , int nodoB );

        void dijkstra( unsigned nodo, 
                       vector<int>& dist,
                       unsigned hasta,
                       vector<int> &path,
                       vector<int> &ign);

        void pathTo( int desde, 
                     int hasta,
                     vector<int> &path,
                     vector<int> &ign );
        
        void pathTo( int desde, 
                     int hasta,
                     list<int> &path,
                     vector<int> &ign );
        
        unsigned coloreo( vector<unsigned> & ordenNodos , vector< list<unsigned> > & colores );
        
        string toString();
        static bool test();

};

/* Grafo( int cantNodos , T& obj )
 * 
 * Crea un grafo con una cantidad de nodos y le
 * asigna a cada nodo un objeto del tipo del
 * grafo.
 * 
 * Argumentos:
 * int cantNodos - Cantidad de nodos a crear.
 * T& obj - Objeto a insertar en cada nodo.
 */
template<class T>
Grafo<T> :: Grafo( int cantNodos = 1 , T& obj = *(new T) ){
    nodos.resize(cantNodos + 1);

    for( int i = 1 ; i <= cantNodos ; i++ ){
        Nodo<T> nodo( i , obj );
        nodos[i] = nodo;
    }    
}

/* ~Grafo()
 * Destructor. Destruye el grafo.
 * 
 * Sin argumentos.
 */
template<class T>
Grafo<T> :: ~Grafo(){
}

/* agregarArco( int nodoA , int nodoB , [int longitud] )
 * Agrega un arco entre 2 nodos y le asigna una longitud.
 * La direccion del arco es del nodo A al nodo B.
 * 
 * Argumentos:
 * int nodoA - Identificador del nodo A.
 * int nodoB - Identificador del nodo B.
 * int longitud - Longitud del arco (opcional).
 */
template<class T>
void Grafo<T> :: agregarArco( int nodoA , int nodoB , int longitud = 1 ){
    nodos[ nodoA ].agregarArco( nodos[ nodoB ] , longitud );
}

/* agregarNodo( [T& obj] )
 * Agrega un nodo y le asigna un objeto.
 * 
 * Argumentos:
 * T& obj - Objeto a asignar al nodo (opcional).
 */
template<class T>
void Grafo<T> :: agregarNodo( T& obj = *(new T) ){
    Nodo<T> nodo( nodos.size() + 1 , obj );        
    nodos.push_back( nodo );
}

/* Nodo<T>& getNodo( int nodo )
 * Retorna el nodo especificado.
 * 
 * Argumentos:
 * int nodo - Identificador de nodo.
 * 
 * Retorno:
 * La funcion retorna el nodo de tipo T 
 * cuyo identificador coincida con el 
 * primer argumento de la funcion.
 */
template<class T>
Nodo<T>& Grafo<T> :: getNodo( int nodo ){
    return nodos[nodo];
}

/* getNodosAdyacentes( int nodo , vector< Nodo<T> >& vec )
 * Busca los nodos adyacentes a otro.
 * 
 * Argumentos:
 * int nodo - Nodo del que se buscan las adyacencias.
 * vector< Nodo<T> >& vec - Vector donde se guardan las adyacencias.
 */
template<class T>
void Grafo<T> :: getNodosAdyacentes( int nodo , vector< Nodo<T> >& vec ){
    vector< Arco<T> > arcos;
    
    nodos[nodo].getArcos(arcos);
    
    for( unsigned int i = 0 ; i < arcos.size() ; i++ )
        vec.push_back( arcos[i].getNodo() );
}

/* getNodosAdyacentes( int nodo , vector<int>& vec )
 * Busca los nodos adyacentes a otro.
 * 
 * Argumentos:
 * int nodo - Nodo del que se buscan las adyacencias.
 * vector<int>& vec - Vector donde se guardan las adyacencias.
 */
template<class T>
void Grafo<T> :: getNodosAdyacentes( int nodo , vector<unsigned>& vec ){
    vector< Arco<T> > arcos;
    
    nodos[nodo].getArcos(arcos);
    
    for( unsigned int i = 0 ; i < arcos.size() ; i++ )
        vec.push_back( arcos[i].getNodo().getNum() );
      
}

template<class T>
bool Grafo<T> :: esAdyacente( int nodoA , int nodoB ){
    vector< Arco<T> > arcos;
    
    nodos[nodoA].getArcos(arcos);
    
    for( unsigned int i = 0 ; i < arcos.size() ; i++ )
         if( arcos[i].getNodo().getNum() == nodoB ) 
            return true;
    
    return false;
}

/* dijkstra( unsigned nodo, 
 *           vector<int>& dist[,
 *           unsigned hasta,
 *           vector<int> &ign,
 *           vector<int> &path] )
 * 
 * Aplica el algoritmo de Dijkstra sobre el grafo
 * para el nodo especificado.
 * 
 * Argumentos:
 * unsigned nodo - Identificador de nodo.
 * 
 * vector<int>& dist - Vector donde se guardaran las distancias.
 * 
 * unsigned hasta - Identificador del nodo hasta el cual se
 *                  ejecutara el algoritmo (opcional).
 * 
 * vector<int> &ign - Vector que contiene los nodos que
 *                    seran ignorados al aplicar el algoritmo (opcional).
 * 
 * vector<int> &path - Vector donde se guardara a traves de que
 *                     nodo se llega al camino minimo para cada
 *                     nodo analizado (opcional).
 */
template<class T>
void Grafo<T> :: dijkstra( unsigned nodo,
                           vector<int>& dist,
                           unsigned hasta = 0,
                           vector<int> &ign = *( new vector<int>(0) ),
                           vector<int> &path = *( new vector<int>(0) ) ){
                             
    int cantNodos = nodos.size(),
        min = 0,
        nodoMin = 0;
    
    vector< Arco<T> > arc;
    dist.clear();
    path.clear();
    dist.resize( cantNodos , INF );
    path.resize( cantNodos , 0 );
   
    for( unsigned i = 0 ; i < ign.size() ; i++ ){
        dist[ ign[i] ] = -INF;
    }
    
    dist[0] = 0;
    
    dist[nodo] = 0;

    int i = 0;
        
    while( i++ < cantNodos - 1 && nodo != hasta ){
        
        nodos[nodo].getArcos( arc );
               
        for( unsigned j = 0 ; j < arc.size() ; j++ ){
            
            if( dist[ arc[j].getNodo().getNum() ] == INF ||
              ( dist[ arc[j].getNodo().getNum() ] > 0 && 
              ( arc[j].getLongitud() + (-1 * dist[nodo]) ) < dist[ arc[j].getNodo().getNum() ] ) ){
            
                dist[ arc[j].getNodo().getNum() ] = arc[j].getLongitud() + ( -1 * dist[nodo] );
                path[ arc[j].getNodo().getNum() ] = nodo;       
            }
            
        }
    
        min = INF;
        nodoMin = nodo;
        
        for( unsigned j = 1 ; j < dist.size() ; j++ ){
            
            if( dist[j] > 0 && dist[j] < min ){
                min = dist[j];
                nodoMin = j;
            }
        }
        
        dist[nodoMin] *= -1;
        nodo = nodoMin;
        
    }
    
    for( unsigned i = 0 ; i < dist.size() ; i++ )
        dist[i] = dist[i] < 0 ? dist[i] *= -1: dist[i] ;
    
}

/* pathTo( int desde, 
 *         int hasta,
 *         vector<int> &path[,
 *         vector<int> &ign] )
 * 
 * Hace el recorrido mas corto entre 2 nodos cualesquiera y
 * carga en un vector los nodos por los cuales pasa para
 * concretar este recorrido.
 * 
 * Argumentos:
 * int desde - Identificador del nodo del cual se empieza
 *             el recorrido.
 * 
 * int hasta - Identificador del nodo del cual se termina
 *             el recorrido.
 * 
 * vector<int> &path - Vector donde se guardara a traves de que
 *                     nodo/s se pasa para recorrer el camino minimo.
 * 
 * vector<int> &ign - Vector que contiene los nodos que
 *                    seran ignorados (opcional).
 */
template<class T>
void Grafo<T> :: pathTo( int desde,
                         int hasta,
                         vector<int> &path,
                         vector<int> &ign = *( new vector<int>(0) ) ){
                           
    vector<int> dist,
                trayectos;
    
    dijkstra( desde , dist , hasta , ign , trayectos );
    
    int nodo = hasta;
    
    path.clear();
       
    path.push_back(hasta);
    
    while( nodo != desde ){
        path.push_back( trayectos[nodo] );
        nodo = trayectos[nodo];
    }
    
    vector<int> :: iterator it = path.begin(),
                            itr = path.end() - 1;
                          
    while(it < itr){
        int aux = 0;
        
        aux = *it;
        *it = *itr;
        *itr = aux;
        
        it++;
        itr--;
    }
   
}


/* pathTo( int desde, 
 *         int hasta,
 *         list<int> &path,
 *         [vector<int> &ign] )
 * 
 * Hace el recorrido mas corto entre 2 nodos cualesquiera y
 * carga en un vector los nodos por los cuales pasa para
 * concretar este recorrido.
 * 
 * Argumentos:
 * int desde - Identificador del nodo del cual se empieza
 *             el recorrido.
 * 
 * int hasta - Identificador del nodo del cual se termina
 *             el recorrido.
 * 
 * list<int> &path - Lista donde se guardara a traves de que
 *                   nodo/s se pasa para recorrer el camino minimo.
 * 
 * vector<int> &ign - Vector que contiene los nodos que
 *                    seran ignorados (opcional).
 */
template<class T>
void Grafo<T> :: pathTo( int desde,
                         int hasta,
                         list<int> &path,
                         vector<int> &ign = *( new vector<int>(0) ) ){
                           
    vector<int> dist,
                trayectos;
    
    dijkstra( desde , dist , hasta , ign , trayectos );
    
    int nodo = hasta;
       
    path.clear();
    
    path.push_front(hasta);
    
    while( nodo != desde ){
        path.push_front( trayectos[nodo] );
        nodo = trayectos[nodo];
    }
   
}

template<class T>
unsigned Grafo<T> :: coloreo( vector<unsigned> & ordenNodos , 
                              vector< list<unsigned> > & colores ){
    
    unsigned nroCromatico = 0;
    
    list<unsigned>::iterator lstIt;
    list<unsigned> lstNodos;
    
    //Paso el vector a lista para así ir eliminando los nodos que ya tienen color.
    for ( unsigned i = 1 ; i < ordenNodos.size() ; i++ )
        lstNodos.push_back( ordenNodos[i] );
    
    //Esto se hace para no tener problemas con los indices.
    {
        list<unsigned> nullColorNodes(0);
            
        colores.clear();
        
        colores.push_back(nullColorNodes);
        
    }
    
    
    while ( ! lstNodos.empty() ){
                
        nroCromatico++;
       
        /*Agrego otro color.*/{
            list<unsigned> nullColorNodes(0);
            colores.push_back(nullColorNodes);
        }
        
        colores[nroCromatico].push_back( lstNodos.front() );
        nodos[lstNodos.front()].setColor( nroCromatico );
        lstNodos.pop_front();
        
        lstIt = lstNodos.begin();
        
        while ( lstIt != lstNodos.end() ){
            vector<unsigned> ady;
            list<unsigned>::iterator lstColIt = 
                        colores[nroCromatico].begin();
            bool adyFlag = false;
            
            getNodosAdyacentes( *lstIt, ady );

            sort( ady.begin(), ady.end() );
                         
            while ( !adyFlag && lstColIt != colores[nroCromatico].end() ){
                
                unsigned i = 0;
                               
                while ( i < ady.size()
                        && *lstColIt > ady[i] ) i++;
                
                
                if ( *lstColIt == ady[i] )
                    adyFlag = true;

                lstColIt++;
                
            }
            
            /*Aca sabemos si es adyacente o no. Hay que tratar eso.*/
            
            if ( ! adyFlag ){
                list<unsigned>::iterator lstItAux = 
                        colores[nroCromatico].begin();
                
                while ( lstItAux != colores[nroCromatico].end() 
                        && *lstIt > *lstItAux )
                    lstItAux++;
                    
                colores[nroCromatico].insert( lstItAux, *lstIt );
                
                nodos[*lstIt].setColor( nroCromatico );
                lstItAux = lstIt;
                lstIt++;
                lstNodos.erase(lstItAux);
            }else
               lstIt++;
               
        }
                 
        
    }
    
    return nroCromatico;
}

//toString
template<class T>
string Grafo<T> :: toString(){
    string grafoToString;
    
    ostringstream stream;

    for(int i = 0; i < nodos.size(); i++)
        stream << nodos[i].toString();
            
    grafoToString = stream.str();

    return grafoToString;
}

//test
template<class T>
bool Grafo<T> :: test(){
     int node1 = 1;
     int node2 = 2 ;
     int node3 = 3 ;
     Grafo<char> graph(3);
     
     graph.agregarArco( node1 , node2 , 4 );
     graph.agregarArco( node1 , node3 , 5 );
     
     vector<unsigned> adyacentes;
     vector<int> distancias;
     
     graph.getNodosAdyacentes( 1 , adyacentes );
     
     for(unsigned i = 0; i < adyacentes.size(); i++)
         cout << adyacentes[i] << endl;
     cout << endl;
     
     graph.dijkstra( 1, distancias );     

     for(unsigned i = 0; i < distancias.size(); i++)
         cout << distancias[i] << endl;
     cout << endl;
     
     vector<int> recorridos;
     
     graph.pathTo( 1 , 3 , recorridos );
     
     for(unsigned i = 0; i < recorridos.size(); i++)
         cout << recorridos[i] << endl;
     cout << endl;
     
     return true;
}


#endif
